use rand::Rng;
fn is_prime(num: u64, sieve: &[bool]) -> bool {
    if num < sieve.len() as u64 {
        return sieve[num as usize];
    }
    /* 
    else if num < 100000000{
        for i in 2..(num as f64).sqrt().ceil() as u64 {
            if i!=2 && i%2==0 {continue;}
            else if num % i == 0 {
                return false;
            }
        }
        return true;
    }*/
    else{
        return miller_rabin(num, 5);
    }
    
}

fn sieve_of_eratosthenes(limit: u64) -> Vec<bool> {
    let mut sieve = vec![true; (limit + 1) as usize];
    sieve[0] = false;
    sieve[1] = false;

    for i in 2..((limit as f64).sqrt() as u64 + 1) {
        if sieve[i as usize] {
            for j in (i * i..=limit).step_by(i as usize) {
                sieve[j as usize] = false;
            }
        }
    }

    sieve
}

fn mod_exp(base: u128, exp: u64, modulus: u128) -> u128 {
    let mut result = 1;
    let mut base = base % modulus;
    let mut exp = exp;

    while exp > 0 {
        if exp % 2 == 1 {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exp /= 2;
    }
    result
}

fn miller_rabin(n: u64, k: u64) -> bool {
    if n <= 1 {
        return false;
    }
    if n == 2 || n == 3 {
        return true; 
    }
    if n % 2 == 0 {
        return false; 
    }

    let mut d = n - 1;
    let mut s = 0;
    while d % 2 == 0 {
        d /= 2;
        s += 1;
    }

    for _ in 0..k {
        let a = rand::thread_rng().gen_range(2..n - 1); 
        let mut x = mod_exp(a as u128, d, n as u128); 

        if x == 1 || x == (n - 1) as u128 {
            continue; 
        }

        let mut is_composite = true;
        for _ in 0..s - 1 {
            x = mod_exp(x, 2, n as u128);
            if x == (n - 1) as u128 {
                is_composite = false;
                break;
            }
        }

        if is_composite {
            return false; 
        }
    }

    true 
}

pub fn min_edge_prime_num(number: u32) -> String {
    let count: f64 = number as f64 / 100.0;
    let mut prime_sum = 3;
    let mut len = 3;

    let sieve_limit = 100000;  
    let sieve = sieve_of_eratosthenes(sieve_limit);

    while (prime_sum as f64) / ((2 * len - 1) as f64) >= count {
        len += 2;
        let  check1 ;
        let  check2 ;
        let  check3 ;

        if len % 3 == 0 {
            check3 = false;
            check1 = is_prime(len * len - len + 1, &sieve);
            check2 = is_prime(len * len - 2 * len + 2, &sieve);
            prime_sum += check1 as u32 + check2 as u32 + check3 as u32;
        } else if len % 3 == 2 {
            check1 = false;
            check2 = is_prime(len * len - 2 * len + 2, &sieve);
            check3 = is_prime(len * len - 3 * len + 3, &sieve);
            prime_sum += check1 as u32 + check2 as u32 + check3 as u32;
        } else {
            check1 = is_prime(len * len - len + 1, &sieve);
            check2 = is_prime(len * len - 2 * len + 2, &sieve);
            check3 = is_prime(len * len - 3 * len + 3, &sieve);
            prime_sum += check1 as u32 + check2 as u32 + check3 as u32;
        }
    }

    format!("{},{}", len, prime_sum)
}

